/*
    有效的括号
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：
        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
*/

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char pairs(char a)
{
    if(a=='}') return '{';
    if(a==']') return '[';
    if(a==')') return '(';
    return 0;
}

bool isValid(char *s)
{
    int n = strlen(s);
    if(n%2==1) return false;    //总共有奇数个括号时一定是false

    char stk[n+1],top=0;         //定义一个栈
    for(int i=0;i<n;i++)
    {
        char ch = pairs(s[i]);
        if(ch) 
        {
            if(top==0||stk[top-1]!=ch) return false;    //栈为空或者弹出的和下一个不匹配
            top--;                
        }
        else
        {
            stk[top++] = s[i];
        }
    }
    return top==0;
}

int main(int argc, char const *argv[])
{
    char str[1000];
    printf("请输入任一个括号：");
    scanf("%s",str);
    int num = isValid(str);
    if(num==0)
        printf("%s\n","false");
    else
        printf("%s\n","true");

    return 0;
}

